import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-06-06
 * Time: 20:52
 */
//LeetCode刷题调试
// 滑动窗口
public class Test {
    /**
     * (1)如果数据量较小，比如长度为1000的情况下，只需要从左往右，找到第一个为1的位置，
     * 将它后续k个位置都进行翻转。顺便修改对应的位置上的值，0变1，1变0，直到后面少于k个时，
     * 返回-1;如果正好能够翻转完毕，则返回翻转次数。这个次数一定是最小的。时间复杂度为O(nk)。这是一个贪心的思想。
     * (2)那么如果我们还是采用这种思想，可以简化翻转这一步操作将它降为O(1)。(3）我们需要实现以下几个接口:
     * (3.1）获取第i位的值;
     * (3.2)从i开始的k 位执行翻转操作;
     * (4)）首先来看翻转操作，用一个长度为 n的数组a，记录当前这个位置的操作次数，比如从i开始的k位执行翻转操作，
     * 其实就是对于两个点执行异或，哪两个点呢?a[i]和a[i+K]这两个位置(第i个位置加一，第i+k个位置减一，
     * 由于只需要讨论奇偶性，所以直接采用异或即可)。
     * (5)获取第i个位置，其实就是求(nums[i] + a[0]+... + a[i])&1，这一步可以通过一次扫描求出来。
     * 所以只需要一次扫描就可以把整个贪心的过程给计算出来了。
     * @param nums
     * @param k
     * @return
     */
    public static int minKBitFlips(int[] nums, int k) {
        int[] a = new int[100100];
        int ans = 0, sum = 0;
        for(int i = 0; i < nums.length; ++i) {
            sum ^= a[i];
            sum &= 1;
            if( ( (sum + nums[i]) & 1) == 0 ) {
                if(i + k > nums.length) {
                    return -1;
                }
                a[i] ^= 1;
                a[i+k] ^= 1;
                ++ans;
                sum ^= 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,1,0,1,0,0,0,1};
        int k = 3;
        System.out.println(minKBitFlips(nums, k));
    }
    public static int minimumDifference(int[] nums, int k) {
        int i = 0;//左区间
        int j = -1;//右区间
        Arrays.sort(nums);
        int len = nums.length;
        int min = 100000000;
        while( j < len -1){
            ++j;
            while(j - i + 1 > k){
                i++;
            }
            if(j - i + 1 == k){
                min = Math.min(min,nums[j] - nums[i]);
            }
        }
        return min;
    }
    public static void main1(String[] args) {
        int[] nums = {3,6,7,9,2};
        int k = 2;
        System.out.println(minimumDifference(nums, k));
    }
}
